package com.gxc.array;

import com.gxc.print.ListPrint;

import java.util.ArrayList;
import java.util.List;

/**
 * 2961. 双模幂运算
 * 给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。
 *
 * 如果满足以下公式，则下标 i 是 好下标：
 *
 * 0 <= i < variables.length
 * ((aibi % 10)ci) % mi == target
 * 返回一个由 好下标 组成的数组，顺序不限 。
 */
public class GetGoodIndices {

    public static void main(String[] args) {
/*        ListPrint.print(handle(new int[][]{
                {2,3,3,10},{3,3,3,1},{6,1,1,4}
        }, 2));*/

        ListPrint.print(handle(new int[][]{
                {31,12,21,24}
        }, 1));
    }

    /**
     *
     * @param variables
     * @param target
     * @return
     */
    public static List<Integer> handle(int[][] variables, int target) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < variables.length; i++) {
            int[] variable = variables[i];
            if (pow(pow(variable[0], variable[1], 10), variable[2], variable[3]) ==  target) {
                list.add(i);
            }
        }
        return list;
    }

    private static int pow(int a, int b, int mod) {
        int res = 1;
        while (b>0) {
            if ((b & 1) !=0) res =res * a%mod;
            a = a * a%mod;
            b = b>>1;
        }
        return res;
    }

    class Solution {
        public List<Integer> getGoodIndices(int[][] variables, int target) {
            List<Integer> ans = new ArrayList<Integer>();
            for (int i = 0; i < variables.length; i++) {
                int[] v = variables[i];
                if (powMod(powMod(v[0], v[1], 10), v[2], v[3]) == target) {
                    ans.add(i);
                }
            }
            return ans;
        }

        public int powMod(int x, int y, int mod) {
            int res = 1;
            while (y != 0) {
                if ((y & 1) != 0) {
                    res = res * x % mod;
                }
                x = x * x % mod;
                y >>= 1;
            }
            return res;
        }
    }

}
